{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Diameter of Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: diameterOfBinaryTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树的直径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵二叉树的根节点，返回该树的 <strong>直径</strong> 。</p>\n",
    "\n",
    "<p>二叉树的 <strong>直径</strong> 是指树中任意两个节点之间最长路径的 <strong>长度</strong> 。这条路径可能经过也可能不经过根节点 <code>root</code> 。</p>\n",
    "\n",
    "<p>两节点之间路径的 <strong>长度</strong> 由它们之间边数表示。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/06/diamtree.jpg\" style=\"width: 292px; height: 302px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3,4,5]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数目在范围 <code>[1, 10<sup>4</sup>]</code> 内</li>\n",
    "\t<li><code>-100 &lt;= Node.val &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [diameter-of-binary-tree](https://leetcode.cn/problems/diameter-of-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [diameter-of-binary-tree](https://leetcode.cn/problems/diameter-of-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]', '[1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            nonlocal res\n",
    "            # left length\n",
    "            left = dfs(node.left)\n",
    "            # right length\n",
    "            right = dfs(node.right)\n",
    "            res = max(res, left+right)\n",
    "            return max(left, right)+1\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 0\n",
    "        self.res = 0\n",
    "        self.helper(root)\n",
    "        return self.res\n",
    "    \n",
    "    def helper(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        # self.res.append(root)\n",
    "        # self.helper\n",
    "        left = self.helper(root.left)\n",
    "        right = self.helper(root.right)\n",
    "        self.res = max(self.res, left + right)\n",
    "        return 1 + max(left, right)\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param root: a root of binary tree\n",
    "    @return: return a integer\n",
    "    \"\"\"\n",
    "    def diameterOfBinaryTree(self, root):\n",
    "        # write your code here\n",
    "        l, m = self.find_depth(root)\n",
    "        return m\n",
    "\n",
    "    def find_depth(self, root):\n",
    "        if not root:\n",
    "            return 0, 0\n",
    "        l, m1 = self.find_depth(root.left) \n",
    "        r, m2 = self.find_depth(root.right) \n",
    "        return max(l, r) + 1 , max(l + r, m1, m2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:        \n",
    "    def diameterOfBinaryTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.ans = 1  # 只是方便处理root为None的情况\n",
    "        def depth(node):\n",
    "            if not node: return 0\n",
    "            L = depth(node.left)\n",
    "            R = depth(node.right)\n",
    "            self.ans = max(self.ans, L+R+1)\n",
    "            return max(L, R) + 1\n",
    "\n",
    "        depth(root)\n",
    "        return self.ans - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if root==None:\n",
    "            return 0\n",
    "        if root.left==None and root.right==None:\n",
    "            return 0\n",
    "        heights = []\n",
    "        def twoHeight(root):\n",
    "            if root.left==None and root.right==None:\n",
    "                heights.append(1)\n",
    "                return 1\n",
    "            hl,hr=0,0\n",
    "            if root.left:\n",
    "                hl = twoHeight(root.left)\n",
    "            if root.right:\n",
    "                hr = twoHeight(root.right)\n",
    "            heights.append(hl+hr)\n",
    "            return max(hl,hr)+1\n",
    "        twoHeight(root)\n",
    "        return max(heights)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 0\n",
    "        if not root.left and not root.right:\n",
    "            return 0\n",
    "        def tree_height_and_diameter(root):\n",
    "            if not root.left and not root.right:\n",
    "                return [1, 0]\n",
    "            l = [0, 0]\n",
    "            r = [0, 0]\n",
    "            if root.left:\n",
    "                l = tree_height_and_diameter(root.left)\n",
    "            if root.right:\n",
    "                r = tree_height_and_diameter(root.right)\n",
    "            height = max(l[0], r[0]) + 1\n",
    "            diameter = 0\n",
    "            if not root.right:\n",
    "                diameter = max(l[1], height - 1)\n",
    "            elif not root.left:\n",
    "                diameter = max(r[1], height - 1)\n",
    "            else:\n",
    "                diameter = max(l[1], r[1], l[0] + r[0])\n",
    "            return [height, diameter]\n",
    "        return tree_height_and_diameter(root)[1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        self.res = 0\n",
    "        \n",
    "        def maxDepth(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            L = maxDepth(node.left)\n",
    "            R = maxDepth(node.right)\n",
    "            self.res = max(self.res, L + R)\n",
    "            return max(L, R) + 1\n",
    "        \n",
    "        maxDepth(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        # 这种题的解法一般就是从根节点开始递归\n",
    "        # 你要分析呀，根节点为root的树的直径可能是什么？无非就是两种情况\n",
    "        # 直径经过根节点，那么直径就是左子树深度＋右子树深度，不经过根节点，那么直径就是左子树直径或者右子树直径\n",
    "        # 最终结果就是这三者的最大值\n",
    "        \n",
    "        if root is None:\n",
    "            return 0\n",
    "        \n",
    "        res = self.depth(root.left) + self.depth(root.right)\n",
    "        return max(res, self.diameterOfBinaryTree(root.left), self.diameterOfBinaryTree(root.right))\n",
    "        \n",
    "    def depth(self, root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        \n",
    "        left_dep = self.depth(root.left)\n",
    "        right_dep = self.depth(root.right)\n",
    "        \n",
    "        return max(left_dep, right_dep) + 1\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import collections\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # [4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2]\n",
    "        if not root: return 0\n",
    "        def hello(root,m):\n",
    "            if not root:return m\n",
    "            return max(hello(root.left,m+1),hello(root.right,m+1))\n",
    "        def new(root):\n",
    "            return hello(root.left,0)+hello(root.right,0)\n",
    "        \n",
    "        return max(new(root),self.diameterOfBinaryTree(root.left),self.diameterOfBinaryTree(root.right))\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def get_root(self, root):\n",
    "        stack = [root]\n",
    "        aux_stack = []\n",
    "        while stack:\n",
    "            for node in stack:\n",
    "                if node.left and node.right:\n",
    "                    return node \n",
    "                if node.left:\n",
    "                    aux_stack.append(node.left)\n",
    "                if node.right:\n",
    "                    aux_stack.append(node.right)\n",
    "            stack = aux_stack\n",
    "            aux_stack = []\n",
    "        return None\n",
    "\n",
    "\n",
    "    def get_depth(self, root):\n",
    "        depth = -1 \n",
    "        if root is None:\n",
    "            return depth\n",
    "        stack = [root]\n",
    "        aux_stack = []\n",
    "        while stack:\n",
    "            depth += 1 \n",
    "            for node in stack:\n",
    "                if node.left:\n",
    "                    aux_stack.append(node.left)\n",
    "                if node.right:\n",
    "                    aux_stack.append(node.right)\n",
    "            stack = aux_stack\n",
    "            aux_stack = []\n",
    "        return depth \n",
    "\n",
    "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        elif not root.left and not root.right:\n",
    "            return 0\n",
    "        res = 0\n",
    "        stack = [root]\n",
    "        aux_stack = []\n",
    "        while stack:\n",
    "            for node in stack:\n",
    "                x = -1\n",
    "                y = -1 \n",
    "                if node.left:\n",
    "                    x = self.get_depth(node.left)\n",
    "                    aux_stack.append(node.left)\n",
    "                if node.right:\n",
    "                    y = self.get_depth(node.right)\n",
    "                    aux_stack.append(node.right)\n",
    "                res = max(x + y + 2, res)\n",
    "            stack = aux_stack\n",
    "            aux_stack = []\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root):\n",
    "        #寻找每一颗树的直径，为左子树的长度+右子树的长度+1. 最后将最大的直径返回\n",
    "        if not root:\n",
    "            return 0\n",
    "        length_list = []\n",
    "        queue = []\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "            if node.right:\n",
    "                queue.append(node.right)  \n",
    "            length_list.append(self.findHeight(node.right) + self.findHeight(node.left))\n",
    "\n",
    "        return max(length_list)\n",
    "    def findHeight(self, root):\n",
    "        if not TreeNode:\n",
    "            return 0\n",
    "        queue = []          #这里的queue是个栈\n",
    "        queue.append((1,root))\n",
    "        height = 0\n",
    "        while queue:\n",
    "            curre_height, node = queue.pop()\n",
    "            if node is not None:\n",
    "                height = max(height, curre_height)\n",
    "                queue.append((curre_height + 1, node.left))\n",
    "                queue.append((curre_height + 1, node.right))\n",
    "        return height"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    def __init__(self):\n",
    "        self.diameter=0\n",
    "\n",
    "    def lgst(self,root:TreeNode)->int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        else:\n",
    "            l=self.lgst(root.left)\n",
    "            r=self.lgst(root.right)\n",
    "            self.diameter=max(self.diameter,l+r)\n",
    "        return max(l,r)+1\n",
    "\n",
    "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        self.lgst(root)\n",
    "        return self.diameter\n",
    "        '''\n",
    "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        dia=0\n",
    "        fg=[]#[是否右孩子标志，左边深度]\n",
    "        st=[]\n",
    "        node=root\n",
    "        lastr=0\n",
    "        while st or node:\n",
    "            if node:\n",
    "                st.append(node)\n",
    "                fg.append([1,0])\n",
    "                node=node.left\n",
    "            elif fg[-1][0]:\n",
    "                fg[-1][0]=0\n",
    "                fg[-1][1]=lastr\n",
    "                lastr=0\n",
    "                node=st[-1].right\n",
    "            else:\n",
    "                dia=max(dia,lastr+fg[-1][1])\n",
    "                lastr=max(lastr,fg[-1][1])+1\n",
    "                fg.pop()\n",
    "                st.pop()\n",
    "        return dia\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        def height(node):\n",
    "            if not node: return 0\n",
    "            queue = [node]\n",
    "            height = 0\n",
    "            while queue:\n",
    "                height += 1\n",
    "                for i in range(len(queue)):\n",
    "                    n = queue.pop(0)\n",
    "                    if n.left: queue.append(n.left)\n",
    "                    if n.right: queue.append(n.right)\n",
    "            return height\n",
    "\n",
    "        if not root: return 0\n",
    "        res = 0\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            n = queue.pop()\n",
    "            res = max(res, height(n.left)+height(n.right))\n",
    "            if n.left: queue.append(n.left)\n",
    "            if n.right: queue.append(n.right)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        def maxdepth(root):\n",
    "            res = 0\n",
    "            current_nodes = [root]\n",
    "            while current_nodes:\n",
    "                res += 1\n",
    "                next_nodes = []\n",
    "                for node in current_nodes:\n",
    "                    if node.left:\n",
    "                        next_nodes.append(node.left)\n",
    "                    if node.right:\n",
    "                        next_nodes.append(node.right)\n",
    "                current_nodes = next_nodes\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        if not root:\n",
    "            return 0\n",
    "        current_nodes = [root]\n",
    "        res = float('-inf')\n",
    "        while current_nodes:\n",
    "            next_nodes = []\n",
    "            for node in current_nodes:\n",
    "                if node.left:\n",
    "                    num_left = maxdepth(node.left)\n",
    "                    next_nodes.append(node.left)\n",
    "                else:\n",
    "                    num_left = 0\n",
    "                if node.right:\n",
    "                    num_right = maxdepth(node.right)\n",
    "                    next_nodes.append(node.right)\n",
    "                else:\n",
    "                    num_right = 0\n",
    "                tmp = abs(num_left + num_right)\n",
    "                res = max(res, tmp)\n",
    "            current_nodes = next_nodes\n",
    "        \n",
    "\n",
    "        return res\n",
    "            \n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        def maxdepth(root):\n",
    "            res = 0\n",
    "            current_nodes = [root]\n",
    "            while current_nodes:\n",
    "                res += 1\n",
    "                next_nodes = []\n",
    "                for node in current_nodes:\n",
    "                    if node.left:\n",
    "                        next_nodes.append(node.left)\n",
    "                    if node.right:\n",
    "                        next_nodes.append(node.right)\n",
    "                current_nodes = next_nodes\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        if not root:\n",
    "            return 0\n",
    "        current_nodes = [root]\n",
    "        res = float('-inf')\n",
    "        while current_nodes:\n",
    "            next_nodes = []\n",
    "            for node in current_nodes:\n",
    "                if node.left:\n",
    "                    num_left = maxdepth(node.left)\n",
    "                    next_nodes.append(node.left)\n",
    "                else:\n",
    "                    num_left = 0\n",
    "                if node.right:\n",
    "                    num_right = maxdepth(node.right)\n",
    "                    next_nodes.append(node.right)\n",
    "                else:\n",
    "                    num_right = 0\n",
    "                tmp = num_left + num_right\n",
    "                res = max(res, tmp)\n",
    "            current_nodes = next_nodes\n",
    "        \n",
    "\n",
    "        return res\n",
    "\n",
    "        \n",
    "            \n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        stack = [[root, 'null']]\n",
    "        re = []\n",
    "        m = 0\n",
    "        while stack:\n",
    "            root,fa = stack.pop()\n",
    "            root.val = 1\n",
    "            re.append([root, fa])\n",
    "            if root.right:\n",
    "                stack.append([root.right, root])\n",
    "            if root.left:\n",
    "                stack.append([root.left, root])\n",
    "        for root,fa in re[::-1]:\n",
    "            if fa != 'null':\n",
    "                m = max([m, fa.val+root.val])\n",
    "                fa.val = max([fa.val, root.val+1])\n",
    "        return max([m-1, 0])  # 小心路径长度是节点数-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.max = 0\n",
    "    \n",
    "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        self.depth(root)\n",
    "        \n",
    "        return self.max\n",
    "        \n",
    "    def depth(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        l = self.depth(root.left)\n",
    "        r = self.depth(root.right)\n",
    "        '''每个结点都要去判断左子树+右子树的高度是否大于self.max，更新最大值'''\n",
    "        self.max = max(self.max, l+r)\n",
    "        \n",
    "        # 返回的是高度\n",
    "        return max(l, r) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.max = 0\n",
    "    \n",
    "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        self.depth(root)\n",
    "        \n",
    "        return self.max\n",
    "        \n",
    "    def depth(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        l = self.depth(root.left)\n",
    "        r = self.depth(root.right)\n",
    "        '''每个结点都要去判断左子树+右子树的高度是否大于self.max，更新最大值'''\n",
    "        self.max = max(self.max, l+r)\n",
    "        \n",
    "        # 返回的是高度\n",
    "        return max(l, r) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        self.res = 0\n",
    "        self.maxDepth(root)\n",
    "        return self.res\n",
    "\n",
    "    def maxDepth(self, root):\n",
    "        if not root: return 0\n",
    "        \n",
    "        L = self.maxDepth(root.left)\n",
    "        R = self.maxDepth(root.right)\n",
    "        \n",
    "        self.res = max(self.res, L + R)\n",
    "        return max(L, R) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        maxl, q = 0, [(root)]\n",
    "        nodes = deque()\n",
    "        while q:\n",
    "            p = q.pop(0)\n",
    "            if p.left: q.append(p.left)\n",
    "            if p.right: q.append(p.right)\n",
    "            nodes.appendleft(p)\n",
    "        \n",
    "        for p in nodes:\n",
    "            l = p.left.val if p.left else 0\n",
    "            r = p.right.val if p.right else 0\n",
    "            maxl = max(l + r, maxl)\n",
    "            p.val = max(l, r) + 1\n",
    "        \n",
    "        return maxl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def post_search(self, root: TreeNode):\n",
    "        q = root\n",
    "        stack = []\n",
    "        queue = []\n",
    "        while q or len(stack) > 0:\n",
    "            if q:\n",
    "                stack.append(q)\n",
    "                queue.append(q)\n",
    "                q = q.right\n",
    "            else:\n",
    "                q = stack.pop()\n",
    "                q = q.left\n",
    "\n",
    "        for i in range(len(queue)-1, -1, -1):\n",
    "            q = queue[i]\n",
    "            left = 0 if q.left is None else q.left.val\n",
    "            right = 0 if q.right is None else q.right.val\n",
    "            self.max_path = max(left + right + 1, self.max_path)\n",
    "            q.val = max(left, right) + 1\n",
    "\n",
    "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        self.max_path = 0\n",
    "        self.post_search(root)\n",
    "        return self.max_path-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        p = root\n",
    "        s = []\n",
    "        r = None\n",
    "        root.dept = 0\n",
    "        maxDept = 0\n",
    "\n",
    "        while s or p:\n",
    "            while p:\n",
    "                s.append(p)\n",
    "                p = p.left\n",
    "\n",
    "            t = s[-1] if s else None\n",
    "            if t.right and t.right != r:\n",
    "                p = t.right  # 不是回路\n",
    "            else:\n",
    "                t = s.pop()\n",
    "                r = t\n",
    "                if not (t.left or t.right):\n",
    "                    # 叶子节点\n",
    "                    t.dept = 1\n",
    "\n",
    "                else:\n",
    "                    lDept = t.left.dept if t.left else 0\n",
    "                    rDept = t.right.dept if t.right else 0\n",
    "                    t.dept = max(lDept, rDept) + 1\n",
    "                    maxDept = max(maxDept, lDept+rDept+1)\n",
    "                    p = None\n",
    "\n",
    "        return max(maxDept -1, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        def length(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            \n",
    "            que = deque([(root, 1)])\n",
    "            while que:\n",
    "                cur, level = que.popleft()\n",
    "                if cur.left:\n",
    "                    que.append((cur.left, level + 1))\n",
    "                if cur.right:\n",
    "                    que.append((cur.right, level + 1))\n",
    "            \n",
    "            return level\n",
    "        \n",
    "        ret = 0\n",
    "        que = deque([root])\n",
    "        while que:\n",
    "            cur = que.popleft()\n",
    "            ret = max(ret, length(cur.left) + length(cur.right))\n",
    "            if cur.left:\n",
    "                que.append(cur.left)\n",
    "            if cur.right:\n",
    "                que.append(cur.right)\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:return 0\n",
    "        index=[root]\n",
    "        depth=[]\n",
    "        res=0\n",
    "        while index:\n",
    "            tmp=index.pop()\n",
    "            if not tmp:\n",
    "                tmp=index.pop()\n",
    "                depth1=depth.pop()\n",
    "                depth2=depth.pop()\n",
    "                depth.append(max(depth1,depth2)+1)\n",
    "                # print(tmp.val,depth1,depth2)\n",
    "                res=max(res,depth1+depth2)\n",
    "                continue\n",
    "            index.append(tmp)\n",
    "            index.append(None)\n",
    "            if tmp.right:\n",
    "                index.append(tmp.right)\n",
    "            else:\n",
    "                depth.append(0)\n",
    "            if tmp.left:\n",
    "                index.append(tmp.left)\n",
    "            else:\n",
    "                depth.append(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        #直径可以理解为某个节点的左子树的最大链长加右子树的最大链长加2\n",
    "        #设计一个计算节点最大链长的函数，顺便就可以把直径算出来\n",
    "        # def dfs(node):\n",
    "        #     if not node:\n",
    "        #         return -1 #这里是-1，因为如果是叶子结点的话，max(l_len,r_len)+1就是-1+1为0了\n",
    "        #     l_len = dfs(node.left)\n",
    "        #     r_len = dfs(node.right)\n",
    "        #     return max(l_len,r_len)+1\n",
    "\n",
    "        ans = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return -1 #这里是-1，因为如果是叶子结点的话，max(l_len,r_len)+1就是-1+1为0了\n",
    "            l_len = dfs(node.left)+1 #这样就是考虑整个左边的长度或者整个右边的长度\n",
    "            r_len = dfs(node.right)+1 \n",
    "            nonlocal ans\n",
    "            ans = max(ans,l_len+r_len)\n",
    "            return max(l_len,r_len)\n",
    "        dfs(root) #从根节点开始遍历了每个节点\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 1\n",
    "\n",
    "    def diameterOfBinaryTree(self, root):\n",
    "        def depth(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            l = depth(node.left)\n",
    "            r = depth(node.right)\n",
    "            self.ans = max(self.ans, l + r + 1)\n",
    "            return max(l, r) + 1\n",
    "        depth(root)\n",
    "        return self.ans-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        last_visit = None \n",
    "        st = []\n",
    "        max_val = 0\n",
    "        while(st or root):\n",
    "            while(root):\n",
    "                st.append(root)\n",
    "                root = root.left\n",
    "            root = st.pop()\n",
    "            if root.right is None or root.right == last_visit:\n",
    "                lv = root.left.val if root.left else 0 \n",
    "                rv = root.right.val if root.right else 0 \n",
    "                max_val = max(max_val,1+lv+rv)\n",
    "                root.val = max(lv,rv) + 1\n",
    "                last_visit = root\n",
    "                root = None\n",
    "                continue\n",
    "            st.append(root)\n",
    "            root = root.right\n",
    "        return max_val -1 if max_val>0 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        #左节点最大层级+右节点最大层级,但是有可能不走跟节点，所以要把每个子节点当成跟节点操作一遍，最后取max\n",
    "        ans = []\n",
    "\n",
    "        left = 0\n",
    "        right = 0\n",
    "\n",
    "        queue1 = [root.left] if root.left else []\n",
    "        queue2 = []\n",
    "        while queue1:\n",
    "            temp = queue1.pop()\n",
    "            ans.append(self.getMaxDistance(temp))\n",
    "            if temp.left:\n",
    "                queue2.append(temp.left)\n",
    "            if temp.right:\n",
    "                queue2.append(temp.right)\n",
    "            if not queue1:\n",
    "                left += 1\n",
    "                if len(queue2)==0:\n",
    "                    break\n",
    "                queue1.extend(queue2)\n",
    "                queue2 = []\n",
    "\n",
    "        queue1 = [root.right] if root.right else []\n",
    "        queue2 = []                \n",
    "        while queue1:\n",
    "            temp = queue1.pop()\n",
    "            ans.append(self.getMaxDistance(temp))\n",
    "            if temp.left:\n",
    "                queue2.append(temp.left)\n",
    "            if temp.right:\n",
    "                queue2.append(temp.right)\n",
    "            if not queue1:\n",
    "                right += 1                \n",
    "                if len(queue2)==0:\n",
    "                    break\n",
    "                queue1.extend(queue2)\n",
    "                queue2 = []\n",
    "        ans.append(right+left)\n",
    "        return max(ans)\n",
    "\n",
    "    def getMaxDistance(self,root: Optional[TreeNode]) -> int :\n",
    "                #左节点最大层级+右节点最大层级\n",
    "        left = 0\n",
    "        right = 0\n",
    "\n",
    "        queue1 = [root.left] if root.left else []\n",
    "        queue2 = []\n",
    "        while queue1:\n",
    "            temp = queue1.pop()\n",
    "            if temp.left:\n",
    "                queue2.append(temp.left)\n",
    "            if temp.right:\n",
    "                queue2.append(temp.right)\n",
    "            if not queue1:\n",
    "                left += 1\n",
    "                if len(queue2)==0:\n",
    "                    break\n",
    "                queue1.extend(queue2)\n",
    "                queue2 = []\n",
    "\n",
    "        queue1 = [root.right] if root.right else []\n",
    "        queue2 = []                \n",
    "        while queue1:\n",
    "            temp = queue1.pop()\n",
    "            if temp.left:\n",
    "                queue2.append(temp.left)\n",
    "            if temp.right:\n",
    "                queue2.append(temp.right)\n",
    "            if not queue1:\n",
    "                right += 1                \n",
    "                if len(queue2)==0:\n",
    "                    break\n",
    "                queue1.extend(queue2)\n",
    "                queue2 = []\n",
    "        return right+left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        recd=defaultdict(int)\n",
    "        stack,ans=[root],0\n",
    "        while stack:\n",
    "            node=stack.pop()\n",
    "            if node:\n",
    "                stack.append(node)\n",
    "                stack.append(None)\n",
    "                if node.left:\n",
    "                    stack.append(node.left)\n",
    "                if node.right:\n",
    "                    stack.append(node.right)\n",
    "            else:\n",
    "                node=stack.pop()\n",
    "                recd[node]=1+max(recd[node.left],recd[node.right])\n",
    "                ans=max(ans,recd[node.left]+recd[node.right])\n",
    "        return ans\n",
    "        '''\n",
    "        def hight(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            return 1+max(hight(root.left),hight(root.right))\n",
    "        def path(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            if not root.left and root.right:\n",
    "                return 0\n",
    "            leng=hight(root.left)+hight(root.right)\n",
    "            return max(leng,path(root.left),path(root.right))\n",
    "        return path(root)\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "         ans = 0\n",
    "         def dfs(node):\n",
    "             if node is None:\n",
    "                 return -1\n",
    "             l_len = dfs(node.left)\n",
    "             r_len = dfs(node.right)\n",
    "             nonlocal ans\n",
    "             ans = max(ans, l_len + r_len + 2)\n",
    "             return max(l_len, r_len) + 1\n",
    "         dfs(root)\n",
    "         return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        if root == None:\n",
    "            return 0\n",
    "        \n",
    "        lDeep = deepOfTree(root.left)\n",
    "        rDeep = deepOfTree(root.right)\n",
    "        diameter = lDeep + rDeep\n",
    "        leftDiamater = self.diameterOfBinaryTree(root.left)\n",
    "        rightDiamater = self.diameterOfBinaryTree(root.right)\n",
    "        return max(diameter, leftDiamater, rightDiamater)\n",
    "\n",
    "def deepOfTree(root: Optional[TreeNode]) -> int:\n",
    "    if root == None:\n",
    "        return 0\n",
    "\n",
    "    lDeep = deepOfTree(root.left)\n",
    "    rDeep = deepOfTree(root.right)\n",
    "    return max(lDeep, rDeep) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res = 0\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            l = dfs(root.left)\n",
    "            r = dfs(root.right)\n",
    "            self.res = max(self.res,l+r+1)\n",
    "            return max(l,r)+1\n",
    "        dfs(root)\n",
    "        return self.res-1\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
